package dichotomy.search.range;
/**
 * @Time 2020/1/14
 * @author 王光浩
 * @Need 给定一个数组找出target值在数组中的第一次出现的下标和最后一次出现的下标。
 * @Thinking 使用第一种二分法。
 *           step:使用两次二分法来分别找出target的左边界和右边界。找左边界：当mid对应下标元素大于等于
 *            target，将later=mid-1，否则将previous=mid+1，最后检验previous对应下标元素是否等于target，
 *            如果等于则更改result数组中的值；找右边界：当mid对应下标元素小于等于target，将previous=mid+1，
 *            否则later=mid-1，最后如果later下标对应的元素值等于target则更改result数组中的值。
 *           复杂度分析：时间复杂度O（2logn），空间复杂度O（1）
 * @First NA，原因，没有考虑later和previous越界情况，加上target大于数组的最大值，则最后prervious=数组的长度，产生
 *        下标越界，当target小于数组最小值，最后later=-1，数组下标越界。
 * @Second AC
 * @date 2020/06/14 ——该算法仍然存在问题[2,2] -> [1,0]
 */
public class MyMethodTwo {
    public int[] searchRange(int[] nums, int target) {
    	int later=nums.length-1;
    	int previous=0;
    	int mid;
    	int[] result={-1,-1};
    	if(nums.length==0)return result;
    	//找左边界
    	while(later>=previous) {
    		mid=previous+(later-previous)/2;
    		if(nums[mid]>=target)
    			later=mid-1;
    		else
    			previous=mid+1;
    	}
    	if(previous<nums.length && nums[previous]==target)result[0]=previous;//防止下标越界
    	//更新late和previous
    	later=nums.length-1;
    	previous=0;
    	//找右边界
    	while(later>=previous) {
    		mid=previous+(later-previous)/2;
    		if(nums[mid]<=target)
    			previous=mid+1;
    		else
    			later=mid-1;
    	}
    	if(later>=0 && nums[later]==target)result[1]=later;//防止下标越界
    	return result;
    }

}
